#include "cache.h"
#include "mm.h"
#include "disk.h"

/* The cache number is static. It should changes as 
 * with the percentage of memory used. */
#define SIZE_CACHE	40
static struct cache Cache[SIZE_CACHE];

#define SIZE_HASH_TABLE	7
static struct cache *hash_table[SIZE_HASH_TABLE];

/* A list of caches in most-recent-used order. */
static struct cache *mru_head, *mru_tail;

static int hash_func(u32_t bn)
{
	return bn % SIZE_HASH_TABLE;
}

/* Add a cache into hash-table. */
static void hash_add(struct cache *p)
{
	int id = hash_func(p->bn);
	struct cache *head = hash_table[id];

	p->hash_next = head;
	if (head)
		head->hash_prev = p;
	hash_table[id] = p;
}

/* Remove a cache from hash-table. */
static void hash_rm(struct cache *p)
{
	int id = hash_func(p->bn);
	struct cache *head = hash_table[id];

	if (p->hash_next)
		p->hash_next->hash_prev = p->hash_prev;

	if (p->hash_prev == head)
		hash_table[id] = p->hash_next;
	else
		p->hash_prev->hash_next = p->hash_next;
}

/* Get the least-recent-used cache. Remove it from the hash table,
 * but not remove it from mru list, which should be done by mru_update(). */
static struct cache *mru_least(void)
{
	if (mru_tail->count != 0)
		/*TODO*/;
	if (mru_tail->dirty == 1)
		flush();
	if (mru_tail->hash_prev)
		hash_rm(mru_tail);
	return mru_tail;
}

/* Move the cache from its former place to the head of mru list. */
static void *mru_update(struct cache *p)
{
	if (p == mru_head)
		return;

	if (p == mru_tail) {
		mru_tail = p->mru_prev;
	} else {
		/* Remove from former place. */
		p->mru_prev->mru_next = p->mru_next;
		p->mru_next->mru_prev = p->mru_prev;
	}

	/* Insert it to the head. */
	p->mru_next = mru_head;
	mru_head->mru_prev = p;
	mru_head = p;
}

static void init_mru(void)
{
	struct cache *p, *q;
	int i;

	mru_head = &Cache[0];
	mru_tail = &Cache[SIZE_CACHE - 1];
	for (p = mru_head, i = 0; i < SIZE_CACHE - 1; i++, p++) {
		q = p + 1;
		p->mru_next = q;
		q->mru_prev = p;
	}
}

static inline int read_block(struct cache* c)
{
	return rdwr_disk(c->bn * SEC_BLK, SEC_BLK, c->buf, WIN_READ, &(c->wait));
}
static inline int write_block(struct cache* c)
{
	return rdwr_disk(c->bn * SEC_BLK, SEC_BLK, c->buf, WIN_WRITE, &(c->wait));
}

/* Get a block.
 * if the block has been in Cache: return it;
 * else: search a cache slot, and read the block from disk only if flag = 0.
 */
struct cache *get_block(u32_t bn, int flag)
{
	struct cache *p;

	/* Search in Cache. */
	for (p = hash_table[hash_func(bn)]; p != NULL; p = p->hash_next) {
		if (p->bn == bn)
			goto out;
	}

	/* Not in Cache. */
	p = mru_least();
	if(p->buf == NULL)
		p->buf = (u8_t *)new_page(0);
	p->bn = bn;
	if (flag == 0) {
		/* Read from disk. */
		read_block(p);
		p->dirty = 0;
	}
	hash_add(p);

out:
	mru_update(p);
	p->count++;
	return p;
}

/* Release a cache. Must be called after get_cache().
 */
void release_block(struct cache *p, int dirty)
{
	p->count--;
	if (dirty != 0)
		p->dirty = 1;
}

void init_cache(void)
{
	init_mru();
}

void flush(void)
{
	int i;
	struct cache *p;

	for (i = 0; i < SIZE_HASH_TABLE; i++) {
		for (p = hash_table[i]; p != NULL; p = p->hash_next) {
			if (p->dirty) {
				write_block(p);
				p->dirty = 0;
			}
		}
	}
}
